Periodische Markow-Kette

Periodische Markow-Kette ist ein Begriff aus der Stochastik und beschreibt eine für die Konvergenz wichtige Eigenschaft einer Markow-Kette. Anschaulich ist eine Markow-Kette periodisch, wenn man trotz der Zufälligkeit des Gesamtsystems exakte Voraussagen darüber treffen kann, in welcher Teilmenge der Zustandsmenge sich das System an einem bestimmten Zeitpunkt befinden wird. Aperiodizität ist besonders wichtig für das Konvergenzverhalten von Markow-Ketten gegen eine Stationäre Verteilung.

Definition

Gegeben sei eine Markow-Kette in diskreter Zeit und mit höchstens abzählbarem Zustandsraum $Z$. Dann ist für alle $i\in Z$ die Menge

$N_{i}:=\{n|P(X_{n}=i|X_{0}=i)>0\}$

der möglichen Rückkehrzeiten zum Startpunkt definiert. Dann heißt $d(i):=\operatorname {ggT} (N_{i})$ die Periode des Zustandes $i$. Hierbei bezeichnet $\operatorname {ggT}$ den größten gemeinsamen Teiler. Ist $P(X_{n}=i|X_{0}=i)=0$ für alle $n>0$, so setzen wir $d(i)=\infty$. Haben alle Zustände der Markow-Kette Periode eins, so heißt diese aperiodisch. Haben alle Zustände dieselbe Periode $d>1$, so heißt die Markow-Kette periodisch mit Periode $d$. Bei periodischen Markow-Ketten kann bei Kenntnis des Startzustandes also immer mithilfe des Zeitpunktes auf den aktuellen Zustand geschlossen werden.

Eigenschaften

• Anschaulich bedeutet dies folgendes: Startet man in einem Zustand mit Periode $d(i)>1$, so kann das System höchstens zu den Zeitpunkten $nd(i)$ zurückkehren.
• Tatsächlich gilt für jeden Zustand $i$ mit Periode $d(i)$, dass ab einem bestimmten Zeitpunkt eine Rückkehr zu jeder Periode möglich ist. Es existiert also ein $N(i)$, so dass $p_{ii}^{nd(i)}>0$ für alle $n>N(i)$
• Miteinander kommunizierende Zustände besitzen dieselbe Periode.
• Demnach besitzen in einer irreduziblen Markow-Kette alle Zustände dieselbe Periode. Die Kette ist also immer periodisch oder aperiodisch.
• Ist der Zustandsraum der Markow-Kette endlich, und existiert eine Potenz der Übergangsmatrix, deren Einträge alle positiv sind, dann ist die Markow-Kette irreduzibel und aperiodisch.
• Eine irreduzible, positiv rekurrente Markow-Kette ist genau dann aperiodisch, wenn sie gegen eine stationäre Verteilung konvergiert.
• Bei einer irreduziblen Markow-Kette mit Periode d lässt sich der Zustandsraum disjunkt zerlegen in

$Z={\dot {\bigcup _{k=0,\dots ,d-1}}}Z_{k}$

so dass wenn $i$ in $Z_{k}$ ist und $p_{ij}>0$ gilt, dann muss $j\in Z_{k+1\operatorname {mod} d}$ gelten. Die Zerlegungen können also nur in einer bestimmten Reihenfolge durchlaufen werden. Damit definiert die Zerlegung einen d-partiten Graph auf dem Übergangsgraph.

• Ist die Markow-Kette nicht irreduzibel, so kann man die Äquivalenzklasse aller mit $i$ kommunizierenden Zuständen betrachten. Diese lässt sich dann wie oben in disjunkte Teilmengen zerlegen, die wieder nur in eine Richtung durchlaufen werden können.
• Ist der Übergangsgraph bipartit und zusammenhängend, so ist die Markow-Kette periodisch mit gerader Periode. Ist er nicht zusammenhängend, so hat immerhin jeder Zustand gerade Periode. Allgemeinere Aussagen mit k-partiten Graphen gelten aber im Allgemeinen nicht.

Beispiel

Endlicher Zustandsraum

Betrachten wir als Beispiel eine Markow-Kette auf dem Zustandsraum $Z=\{1,2,3,4\}$ und mit Übergangsmatrix

$M={\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0{,}5&0&0{,}5\\1&0&0&0\\\end{pmatrix}}$.

Da die $n$-Schritt-Übergangswahrscheinlichkeiten genau die Diagonaleinträge der $n$-ten Potenz der Übergangsmatrix sind, überprüft man diese auf Positivität. Es gilt

$M^{2}=0{,}5\cdot {\begin{pmatrix}0&0&2&0\\0&1&0&1\\1&0&1&0\\0&2&0&0\\\end{pmatrix}},\quad M^{3}=0{,}25\cdot {\begin{pmatrix}0&2&0&2\\2&0&2&0\\0&3&0&1\\0&0&4&0\\\end{pmatrix}},\quad M^{4}=0{,}25\cdot {\begin{pmatrix}2&0&2&0\\0&3&0&1\\1&0&3&0\\0&2&0&2\\\end{pmatrix}}.$

Das schachbrettartige Muster von $M^{4}$ bleibt bei allen höheren Potenzen erhalten, nur die Null- und die Nichtnulleinträge alternieren. Damit bekommen wir $N_{1}=\{4,6,8,\dotsc \}$, und die Periode des Zustandes 1 ist zwei. Da alle Zustände miteinander kommunizieren, ist damit die Periode der Markow-Kette auch zwei. Die disjunkte Zerlegung des Zustandsraumes ist $Z_{0}=\{1,3\}$ und $Z_{1}=\{2,4\}$.

Abzählbarer Zustandsraum

Betrachten wir als Beispiel eine homogene Markow-Kette auf dem Zustandsraum $\mathbb {Z}$ mit Übergangswahrscheinlichkeiten

$P(X_{n}=k|X_{n-1}=l):={\begin{cases}1/2&{\text{falls }}\quad k=l+1\\1/2&{\text{falls }}\quad k=l-1\\0&\quad \quad \quad {\text{sonst}}\end{cases}}$.

Dies lässt sich mit einem Betrunkenen vergleichen, der entweder nach links oder nach rechts taumelt, dies aber immer mit derselben Wahrscheinlichkeit (siehe Drunkard’s Walk). Dann ist für den Zustand 0 $N_{0}=2\mathbb {N}$ und damit dann auch $d(0)=2$, da eine Rückkehr zum Ursprung immer nur zu geraden Zeitpunkten möglich ist. Dasselbe Ergebnis gilt auch für alle anderen Zustände, damit ist die Markow-Kette periodisch. Würde an einem beliebigen Zustand $l$ der Kette eine kleine Wahrscheinlichkeit eingeführt, in demselben Zustand zu verharren, so wäre die Markow-Kette nicht mehr periodisch, da z. B. $N_{0}=2\mathbb {N} \cup \{2l+1+\mathbb {N} \}$ gilt. Ab dem $2l+1$-ten Zeitschritt sind dann also beliebige Rückkehrzeiten möglich.

Ein Beispiel für eine periodische Markow-Kette mit endlichem Zustandsraum ist das Ehrenfest-Modell.

Literatur

• Ulrich Krengel: Einführung in die Wahrscheinlichkeitstheorie und Statistik. 8. Auflage, Vieweg, 2005. ISBN 978-3-8348-0063-3
• Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik, 4. Auflage, de Gruyter, 2009. ISBN 978-3-11-021526-7
• Christian Hesse: Angewandte Wahrscheinlichkeitstheorie: eine fundierte Einführung mit über 500 realitätsnahen Beispielen und Aufgaben, Vieweg, Braunschweig/Wiesbaden 2003, ISBN 978-3-528-03183-1.